﻿// 0919train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <limits>
#include <iomanip>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <deque>

using namespace std;

/*
输入描述
每个输入包含1个测试用例。每个测试用例第一行给出链表首节点的地址、节点总个数为正整数N (N≤105）
节点的地址是5位非负整数，NULL地址用-1表示
接下来有N行，每行格式为：
Address Data Next
其中Adress是节点地址，Data是该节点保存的 整数数据，Next是下一个节点的地址

输出描述
对每个测试用例，在一行中输出L中间节点保存的数据
如果有两个中间节点，则输出第二个中间节点保存的数据
补充说明：
以确保输入的节点所构成的链表L不会成环，但会存在部分输入节点不属于链表L的情况

输入
00100 4
00000 4 -1
00100 1 12309
33218 3 00000
12309 2 33218
输出
3
 */

class Solution01
{
public:
    struct Node
    {
        string curr, val, next;
        Node() = default;
        Node(string&curr,string&val, string&next): curr(curr),val(val), next(next) {};
    };
    Solution01(vector<string>&base_v, vector<vector<string>>&origin_vec)
    {
    	unordered_map<string, Node>node_map;

        for (auto&item:origin_vec)
        {
            string key = item[0];
            Node node(item[0], item[1], item[2]);
            node_map[key] = node;
	        //for---
        }

        int target_i = stoi(base_v[1]) / 2;

        string first_ptr = base_v[0];
        Node first_node = node_map[first_ptr];
        deque<Node>bfs_queue;
        bfs_queue.push_back(first_node);
        int curr_i = 0;

        string result;
        while (!bfs_queue.empty())
        {
            Node top_node = bfs_queue.front();
            bfs_queue.pop_front();

            if (curr_i==target_i)
            {
                result = top_node.val;
                break;
            }

            string next_ptr = top_node.next;
            Node next_node = node_map[next_ptr];
            bfs_queue.push_back(next_node);
            curr_i++;
            //while
        }
        cout << result;
	    //Solution01
    }
};


/*
给出数字K，请输出所有结果小于K的整数组合到一起的最少交换次数
组合一起是指满足条件的数字相邻，不要求相邻后在数组中的位置
数据范围：
- -100 <= K <= 100
- -100 <= 数组中数值 <= 100

输入描述
第一行输入数组，用空格隔开。譬如：1 3 1 4 0
第二行输入K数值。譬如：2

输出描述
第一行输出最少交换次数。譬如：1

示例
输入
1 3 1 4 0
2
输出
1
小于2的表达式是1 1 0, 共三种可能将所有符合要求数字组合一起，最少交换1次
 */
class Solution02
{
public:
    Solution02(vector<int>&origin_vec, int K)
    {
        //小于K的数标为0，大于等于k的标为1
        int win_length = 0;
        vector<int>num_vec;
        for (auto&num:origin_vec)
        {
            if (num < K)
            {
                num_vec.push_back(0);
                win_length += 1;
            }
            else num_vec.push_back(1);
        }
        //找到num_vec中，包含全部0，且包含1最少的固定滑窗
        int curr_count = 0, min_count = 0;

        int v_size = num_vec.size();
        for (int i=0; i<win_length; i++)
        {
            if (num_vec[i]==1)
            {
                curr_count += 1;
            }
	        //for
        }
        min_count = curr_count;
        int old_left = 0;
        for (int left=1,right=win_length; right<v_size; left++,right++)
        {
            if (num_vec[old_left]==1)
            {
                curr_count -= 1;
            }
            if (num_vec[right]==1)
            {
                curr_count += 1;
            }
            min_count = min(curr_count, min_count);
            old_left = left;
        }

        cout << min_count;
	    //Solution02
    }
};


/*
单词接龙的规则是：
可用于接龙的单词首字母必须要前一个单词的尾字母相同
当存在多个首字母相同的单词时，取长度最长的单词，
如果长度也相等，则取字典序最小的单词；
已经参与接龙的单词不能重复使用
现给定一组全部由小写字母组成单词数组，并指定其中的一个单词作为起始单词，进行单词接龙，
请输出最长的单词串，单词串是单词拼接而成，中间没有空格

输入描述
输入的第一行为一个非负整数，表示起始单词在数组中的索引 K，0 <= K < N 
输入的第二行为一个非负整数，表示单词的个数N；
接下来的N行，分别表示单词数组中的单词
备注：
单词个数N的取值范围为[1,20];
单个单词的长度的取值范围为[1,30]

输出描述
输出一个字符串，表示最终拼接的单词串

输入
0
6
word
dd
da
dc
dword
d
输出
worddwordda

先确定起始单词word，再接以d开头的且长度最长的单词dword
剩余以d开头且长度最长的有dd、da、dc，则取字典序最小的da，所以最后输出worddwordda
 */
class Solution03
{
public:
    Solution03(int start_i, vector<string>&origin_vec)
    {
/*
当存在多个首字母相同的单词时，取长度最长的单词
如果长度也相等，则取字典序最小的单词
已经参与接龙的单词不能重复使用
*/
        string start_str = origin_vec[start_i];
        string result = start_str;
        unordered_set<string>used;
        used.insert(start_str);

        vector<string>sort_vec = origin_vec;
        sort(sort_vec.begin(), sort_vec.end(), [](string& str_1, string& str_2)
            {
                if (str_1.size()==str_2.size())
                {
                    return str_1 < str_2;
                }
                return str_1.size() > str_2.size();
            });

        string last_word = start_str;
        while (true)
        {
            bool is_find = false;
            int str_size = last_word.size();
            char search_ch = last_word[str_size - 1];

            for (auto&str:sort_vec)
            {
	            if (str[0]==search_ch &&used.count(str)==0)
	            {
                    result += str;
                    used.insert(str);
                    last_word = str;
                    is_find = true;
                    break;
	            }
            }
            if (!is_find) break;
        }
        cout << result;
	    //Solution03
    }
};

int main()
{
	{
        int start_i;
        cin >> start_i;

        int v_size;
        cin >> v_size;

        vector<string>origin_vec(v_size);
        for (int i=0; i<v_size; i++)
        {
            cin >> origin_vec[i];
        }

        Solution03 solu(start_i, origin_vec);

        return 0;
	}
	{
        string input;
        getline(cin, input);
        stringstream oh_sstream(input);
        string token;
        vector<int>num_vec;
        while (oh_sstream>>token)
        {
            num_vec.push_back(stoi(token));
        }

        int K;
        cin >> K;

        Solution02 solu(num_vec, K);

        return 0;
	}
/*
00100 4
00000 4 -1
00100 1 12309
33218 3 00000
12309 2 33218
 */
    string first_ptr, total;
    cin >> first_ptr >> total;
    cin.ignore();

    vector<vector<string>>origin_vec;
    string input;
    while (getline(cin,input))
    {
        if (input.empty()) break;
        stringstream oh_sstream(input);
        string token;
        vector<string>item;
        while (oh_sstream>>token)
        {
            item.push_back(token);
        }
        origin_vec.push_back(item);
    }
    vector<string>base_v = { first_ptr, total };
    Solution01 solu(base_v, origin_vec);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
